package org.example.day;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/15 0:23
 */

//你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。
//
//当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。
//
//请你返回完成所有任务的情况下，电脑最少需要运行多少秒。
//
//
//
//示例 1：
//
//输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
//输出：2
//解释：
//- 第一个任务在闭区间 [2, 2] 运行。
//- 第二个任务在闭区间 [5, 5] 运行。
//- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
//电脑总共运行 2 个整数时间点。
//示例 2：
//
//输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
//输出：4
//解释：
//- 第一个任务在闭区间 [2, 3] 运行
//- 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
//- 第三个任务在闭区间 [5, 6] 运行。
//电脑总共运行 4 个整数时间点。
//
//
//提示：
//
//1 <= tasks.length <= 2000
//tasks[i].length == 3
//1 <= starti, endi <= 2000
//1 <= durationi <= endi - starti + 1
public class Solution2589 {

    public static void main(String[] args) {
        Solution2589 solution2589 = new Solution2589();
        int[][] tasks = {{68,129,2},{58,86,9},{112,142,10},{106,108,1},{48,48,1},{116,143,2},{28,43,5},{1,1,1},{75,83,3},{104,136,10},{11,11,1},{60,63,1},{73,111,8},{57,57,1},{117,119,3},{25,38,2},{20,21,1},{78,80,2},{17,17,1},{28,28,1},{77,117,3},{76,109,4},{61,61,1},{84,92,5},{18,41,4},{47,55,9},{74,132,6},{53,87,3},{102,131,7},{26,26,1},{66,68,3},{59,73,1},{22,30,9},{9,13,2},{31,35,2},{90,91,2},{72,72,1},{62,84,8},{105,106,2},{3,3,1},{32,32,1},{99,103,4},{45,52,4},{108,116,3},{91,123,8},{89,114,4},{94,130,7},{103,104,2},{14,17,4},{63,66,4},{98,112,7},{101,140,9},{58,58,1},{109,145,1},{8,15,8},{4,16,5},{115,141,1},{40,50,4},{118,118,1},{81,120,7}};
        System.out.println(solution2589.findMinimumTime4(tasks));
    }

    /**
     * @Description: 当出现频次相同的数字出现时，目前采取的策略是随机选择了一个。 判断这个处理逻辑不是最优解
     *
     * @auther: wyatt
     * @date: 14:51 2024/5/15
    */
    @Deprecated
    public int findMinimumTime(int[][] tasks) {

        int count = 0;
        int n = tasks.length;
        int duration = 0;

        //找到同一个时间片 利用率最高
        HashMap<Integer, List<Integer>> durationMap = new HashMap<>();
        int[] countArr = new int[n];

        for(int i=0;i<n;i++){
            duration += tasks[i][2];
            countArr[i] = tasks[i][2];
            List<Integer> list = new ArrayList<>();
            for(int j=tasks[i][0];j<=tasks[i][1];j++){
                list.add(j);
            }
            durationMap.put(i, list);
        }

        while(duration > 0){

            HashMap<Integer, Integer> countMap = new HashMap<>();
            int max = Integer.MIN_VALUE;
            int maxValue = Integer.MIN_VALUE;
            //找出出现高频的时间片（所有可能的值）
            for(Integer key : durationMap.keySet()){
                if(countArr[key] <= 0){
                    continue;
                }
                if(durationMap.get(key).size() == countArr[key]){
                    maxValue = durationMap.get(key).get(0);
                    break;
                }
                for(Integer i : durationMap.get(key)){
                    if(countMap.containsKey(i)){
                        countMap.put(i, countMap.get(i)+1);
                    }else {
                        countMap.put(i, 1);
                    }
                    if(max < countMap.get(i)){
                        max = countMap.get(i);
                        maxValue = i;
                    }
                }
            }

            //减去高频的时间片， maxMap--
            if(maxValue > 0){
                count++;
                int maxKeyCount = 0;
                for(Integer key : durationMap.keySet()){
                    if(countArr[key] > 0 && durationMap.get(key).contains(maxValue)){
                        countArr[key] = countArr[key]-1;
                        duration--;
                        maxKeyCount++;
                        durationMap.get(key).remove(Integer.valueOf(maxValue));
                    }
                }
                System.out.println(maxValue + "," + maxKeyCount);
            }

        }

        return count;
    }

    //贪心算法，由于已经按照右区间排序
    //顺序的集合 跟 后面的集合，要么是交接，要么是子集， 且右包含， 所以集合先从左剔除已经执行的i，再从后侧开始执行
    public int findMinimumTime4(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        int ans = 0;
        int max = tasks[tasks.length - 1][1];
        boolean[] run = new boolean[max + 1];
        Arrays.fill(run, false);

        for(int[] task : tasks){
            int count = task[2];
            for(int i=task[0]; i<= task[1];i++){
                if(run[i] && count > 0){
                    count--;
                }
            }

            for(int j=task[1];count>0;j--){
                if(!run[j]){
                    run[j] = true;
                    count--;
                    ans++;
                }
            }
        }
        return ans;
    }

    public int findMinimumTime3(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        int ans = 0;
        int mx = tasks[tasks.length - 1][1];
        boolean[] run = new boolean[mx + 1];
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int[] t : tasks) {
            int start = t[0];
            int end = t[1];
            int d = t[2];
            for (int i = start; i <= end; i++) {
                if (run[i] && d >0) {
                    d--; // 去掉运行中的时间点
                    countMap.put(i, countMap.get(i) + 1);
                }
            }
            for (int i = end; d > 0; i--) { // 剩余的 d 填充区间后缀
                if (!run[i]) {
                    System.out.println(i);
                    countMap.put(i, 1);
                    run[i] = true; // 运行
                    d--;
                    ans++;
                }
            }
        }
        System.out.println(countMap);
        return ans;
    }


    public int findMinimumTime2(int[][] tasks) {
        int res = 0;
        for (int i = 1; ; i++) {
            boolean finished = true, run = false;
            for (int[] task : tasks) {
                if (task[2] > 0 && task[1] - i + 1 == task[2]) {
                    run = true;
                }
                if (i <= task[1]) {
                    finished = false;
                }
            }
            if (finished) {
                break;
            }

            if (run) {
                for (int[] task : tasks) {
                    if (i >= task[0] && i <= task[1] && task[2] > 0) {
                        task[2]--;
                    }
                }
                res++;
            }
        }
        return res;
    }


}
